%{
#include <cstdio>
#include <cstring>

// 词法分析头文件
#include "FlexLexer.h"

// bison生成的头文件
#include "BisonParser.h"

// 抽象语法树函数定义原型头文件
#include "AST.h"

// LR分析失败时所调用函数的原型声明
void yyerror(char * msg);

%}

// 联合体声明，用于后续终结符和非终结符号属性指定使用
%union {
    class ast_node * node;

    struct digit_int_attr integer_num;
    struct digit_real_attr float_num;
    struct var_id_attr var_id;
	struct var_type_attr var_type;
};

// 文法的开始符号
%start  CompileUnit

// 指定文法的终结符号，<>可指定文法属性
// 对于单个字符的算符或者分隔符，在词法分析时可直返返回对应的字符即可
%token <integer_num> T_DIGIT
%token <var_id> T_ID
%token <var_type> INT VOID
%token T_FUNC T_RETURN T_ADD T_SUB 
T_MUL T_DIV T_MOD T_SADD T_SSUB T_LTQUAL T_GTEQUAL 
T_EQUAL T_NEQUAL OR AND NOT IF ELSE WHILE BREAK CONTINUE 

//规定了优先级避免二义性
%left T_ADD T_SUB
%left T_MUL T_DIV T_MOD

%type <node> CompileUnit

// 指定文法的非终结符号，<>可指定文法属性
%type <node> FuncDef
%type <node> FuncDecl
%type <node> FuncFormalParams
%type <node> Block

%type <node> FuncFormalParam
%type <node> FuncBasicParam

%type <node> BlockItemList
%type <node> BlockItem

%type <node> Statement
%type <node> Expr
%type <node> Exp UnaryExp SelfExp LVal VarDecl VarInit VarDefs
%type <node> RelatExp LogicExp
%type <node> PrimaryExp
%type <node> RealParamList
%type <node> IfBlock Condition ElseIf WhileBlock

%%

/* 编译单元可包含若干个函数，main函数作为程序的入口，必须存在 */
CompileUnit : FuncDef {
        $$ = create_contain_node(ast_operator_type::AST_OP_COMPILE_UNIT, $1);
        ast_root = $$;
    }
    | Statement {
        $$ = create_contain_node(ast_operator_type::AST_OP_COMPILE_UNIT, $1);
        ast_root = $$;
    }
	| FuncDecl {
		$$ = create_contain_node(ast_operator_type::AST_OP_COMPILE_UNIT, $1);
        ast_root = $$;
	}
    | CompileUnit FuncDef {
        $$ = insert_ast_node($1, $2);
    }
    | CompileUnit Statement {
        $$ = insert_ast_node($1, $2);
    }
	| CompileUnit FuncDecl {
		$$ = insert_ast_node($1, $2);
	}
    ;

// 函数定义
FuncDef : INT T_ID '(' ')' Block  {
	    ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
        $$ = insert_ast_node(create_func_def($2.lineno, $2.id, $5, nullptr),return_node);
    }
    | INT T_ID '(' FuncFormalParams ')' Block {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
		$$ = insert_ast_node(create_func_def($2.lineno, $2.id, $6, $4),return_node);
    }
	| VOID T_ID '(' ')' Block  {
	    ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
        $$ = insert_ast_node(create_func_def($2.lineno, $2.id, $5, nullptr),return_node);
    }
    | VOID T_ID '(' FuncFormalParams ')' Block {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
		$$ = insert_ast_node(create_func_def($2.lineno, $2.id, $6, $4),return_node);
    }
    ;

FuncDecl : INT T_ID '(' ')' ';' {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
        ast_node * decl_node = new_ast_node(ast_operator_type::AST_OP_FUNC_DECL, return_node, nullptr);
		decl_node->name = $2.id;
		$$ = decl_node;
    }
	| INT T_ID '(' FuncFormalParams ')' ';' {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
        ast_node * decl_node = new_ast_node(ast_operator_type::AST_OP_FUNC_DECL, $4, return_node, nullptr);
		decl_node->name = $2.id;
		$$ = decl_node;
	}
	| VOID T_ID '(' ')' ';' {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
        ast_node * decl_node = new_ast_node(ast_operator_type::AST_OP_FUNC_DECL, return_node, nullptr);
		decl_node->name = $2.id;
		$$ = decl_node;
    }
	| VOID T_ID '(' FuncFormalParams ')' ';' {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
        free($1.id);
	    ast_node * return_node = new_ast_node(ast_operator_type::AST_OP_FUNC_RETURN, type_node, nullptr);
        ast_node * decl_node = new_ast_node(ast_operator_type::AST_OP_FUNC_DECL, $4, return_node, nullptr);
		decl_node->name = $2.id;
		$$ = decl_node;
	}
	;    


// 函数参数
FuncFormalParams : FuncFormalParam  {
        $$ = create_contain_node(ast_operator_type::AST_OP_FUNC_FORMAL_PARAMS, $1);
    }
    | FuncFormalParams ',' FuncFormalParam {
        $$ = insert_ast_node($1, $3);
    }
    ;

// 函数参数，目前只支持基本类型参数
FuncFormalParam : FuncBasicParam  {
        $$ = $1;
    }
    ;

// 基本类型函数参数，默认整型
FuncBasicParam : INT T_ID {
        $$ = create_func_formal_param($2.lineno, $2.id);
    }
    ;

// 语句块
Block : '{' '}' {
        // 语句块没有语句
        $$ = nullptr;
    }
    | '{' BlockItemList '}' {
        // 语句块含有语句
        $$ = $2;
    }
    ;

// 语句块内语句列表
BlockItemList : BlockItem {
        // 第一个左侧的孩子节点归约成Block父节点，后续语句可不断作为孩子追加到block中
        // 创建一个AST_OP_BLOCK类型的中间节点，孩子为Statement($1)
        $$ = new_ast_node(ast_operator_type::AST_OP_BLOCK, $1, nullptr);
    }
    | BlockItemList BlockItem  {
        // 采用左递归的文法产生式，可以使得Block节点在上个产生式创建，后续递归追加孩子节点
        // 请注意，不要采用右递归，左递归翻遍孩子的追加
        // BlockItem($2)作为Block($1)的孩子 
        $$ = insert_ast_node($1, $2);
    }
    ;

// 目前语句块内项目只能是语句
BlockItem : Statement  {
        $$ = $1;
    }
    ;

/* 语句 */
Statement : T_ID '=' Expr ';' {
        // 归约到Statement时要执行的语义动作程序
        // 赋值语句，不显示值

        // 变量节点
        ast_node * id_node = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});

        free($1.id);

        // 创建一个AST_OP_ASSIGN类型的中间节点，孩子为Id和Expr($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_ASSIGN, id_node, $3, nullptr);
    }
	| VarDecl ';'{
        $$ = $1;
	}
    | Expr ';' {
        // Expr归约到Statement时要执行的语义动作程序
        // 表达式语句，不显示表达式的值

        // 创建一个AST_OP_EXPR类型的中间节点，孩子为Expr($1)
        $$ = new_ast_node(ast_operator_type::AST_OP_EXPR, $1, nullptr);
    }
    | Expr {
        // Expr归约到Statement时要执行的语义动作程序
        // 表达式语句，需要显示表达式的值

        // 创建一个AST_OP_EXPR_SHOW类型的中间节点，孩子为Expr($1)
        $$ = new_ast_node(ast_operator_type::AST_OP_EXPR_SHOW, $1, nullptr);
    }
	| LogicExp {
        // Expr归约到Statement时要执行的语义动作程序
        // 表达式语句，需要显示表达式的值

        // 创建一个AST_OP_EXPR_SHOW类型的中间节点，孩子为Expr($1)
        $$ = new_ast_node(ast_operator_type::AST_OP_EXPR_SHOW, $1, nullptr);
    }
	| IfBlock {
		$$ = $1;
	}
	| ElseIf {
		$$ = $1;
	}
	| WhileBlock {
		$$ = $1;
	}
    | T_RETURN Expr ';' {
        // 返回语句
        $$ = new_ast_node(ast_operator_type::AST_OP_RETURN_STATEMENT, $2, nullptr);
    }
	| T_RETURN LogicExp ';' {
        // 返回语句
        $$ = new_ast_node(ast_operator_type::AST_OP_RETURN_STATEMENT, $2, nullptr);
    }
    ;

VarDecl :INT VarDefs {
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
		free($1.id);
		$$ = insert_ast_node( $2, type_node);
	}
	| VarInit {
		$$ = $1;
	}
	;

VarDefs : VarDefs ',' T_ID {
		ast_node * id_node = new_ast_leaf_node(var_id_attr{$3.id, $3.lineno});
		free($3.id);
		$$ = insert_ast_node( $1, id_node);
    }
	| T_ID {
		ast_node * id_node = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});
		free($1.id);
		$$ = new_ast_node(ast_operator_type::AST_OP_VARDECL, id_node, nullptr);
	}
	;

VarInit : INT T_ID '=' Expr {

        ast_node * id_node = new_ast_leaf_node(var_id_attr{$2.id, $2.lineno});
        
		ast_node * type_node = new_ast_leaf_node(var_type_attr{$1.id, $1.lineno});
		
		free($1.id);
        free($2.id);

	    // 创建一个AST_OP_ASSIGN类型的中间节点，孩子为Id和Expr($4)
        $$ = new_ast_node(ast_operator_type::AST_OP_VARINIT, id_node, $4, type_node, nullptr);
    }
	;
Expr : Exp {
        $$ = $1;
    }
	| SelfExp{
		$$ = $1;
	}
    ;

/* 逻辑表达式 */
LogicExp : LogicExp AND LogicExp {
        $$ = new_ast_node(ast_operator_type::AST_OP_AND, $1, $3, nullptr);
    }
    | LogicExp OR LogicExp{
        $$ = new_ast_node(ast_operator_type::AST_OP_OR, $1, $3, nullptr);
    }
	| NOT '(' LogicExp ')'{
        $$ = new_ast_node(ast_operator_type::AST_OP_NOT, $3, nullptr);
    }
	| RelatExp{
		$$ = $1;
	}
	;
/* 关系表达式 */
RelatExp : Exp '>' Exp{
     $$ = new_ast_node(ast_operator_type::AST_OP_GTE, $1, $3, nullptr);
    }
    | Exp '<' Exp{
     $$ = new_ast_node(ast_operator_type::AST_OP_LTE, $1, $3, nullptr);
    }
	| Exp T_GTEQUAL Exp{
     $$ = new_ast_node(ast_operator_type::AST_OP_GTEQUAL, $1, $3, nullptr);
    }
	| Exp T_LTQUAL Exp{
     $$ = new_ast_node(ast_operator_type::AST_OP_LTQUAL, $1, $3, nullptr);
    }
    | Exp T_EQUAL Exp{
     $$ = new_ast_node(ast_operator_type::AST_OP_EQUAL, $1, $3, nullptr);
    }
	| Exp T_NEQUAL Exp{
     $$ = new_ast_node(ast_operator_type::AST_OP_NEQUAL, $1, $3, nullptr);
    }
    ;



/* 算数表达式 */
Exp : Exp T_ADD Exp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_ADD, $1, $3, nullptr);
    }
    | Exp T_SUB Exp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_SUB, $1, $3, nullptr);
    }
	| Exp T_MUL Exp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_MUL, $1, $3, nullptr);
    }
    | Exp T_DIV Exp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_DIV, $1, $3, nullptr);
    }
    | Exp T_MOD Exp {
        /* Expr = Expr + Term */

        // 创建一个AST_OP_ADD类型的中间节点，孩子为Expr($1)和Term($3)
        $$ = new_ast_node(ast_operator_type::AST_OP_MOD, $1, $3, nullptr);
    }
	| T_SUB Exp {
		$$ = new_ast_node(ast_operator_type::AST_OP_SUB, $2, nullptr);
	}
    | UnaryExp {
        /* Expr = Term */
        $$ = $1;
    }
    ;

SelfExp : T_SSUB LVal{
      $$ = new_ast_node(ast_operator_type::AST_OP_SSUB, $2, nullptr);
    }
    | T_SADD LVal{
      $$ = new_ast_node(ast_operator_type::AST_OP_SADD, $2, nullptr);
	}
	;
UnaryExp : PrimaryExp {
        $$ = $1;
    }
    | T_ID '(' ')' {
        // 用户自定义的不含实参的函数调用
        $$ = create_func_call($1.lineno, $1.id, nullptr);
    }
    | T_ID '(' RealParamList ')' {
        // 用户自定义的含有实参的参数调用
        $$ = create_func_call($1.lineno, $1.id, $3);
    }
    ;
PrimaryExp :  '(' Expr ')' {
        /* PrimaryExp = Expr */
        $$ = $2;
    }
    | T_DIGIT {
        // 无符号整数识别

        // 终结符作为抽象语法树的叶子节点进行创建
        $$ = new_ast_leaf_node(digit_int_attr{$1.val, $1.lineno});
    }
    | LVal  {
        // 左值
        $$ = $1;
    }
    ;

LVal : T_ID {
        // 终结符作为抽象语法树的叶子节点进行创建
        $$ = new_ast_leaf_node(var_id_attr{$1.id, $1.lineno});

        // 对于字符型字面量的字符串空间需要释放，因词法用到了strdup进行了字符串复制
        free($1.id);
    }
	;

IfBlock : IF '(' Condition ')' Block {
        $$ = new_ast_node(ast_operator_type::AST_OP_IF, $3, $5, nullptr);
    }
	| IF '(' Condition ')' Statement {
		$$ = new_ast_node(ast_operator_type::AST_OP_IF, $3, new_ast_node(ast_operator_type::AST_OP_BLOCK, $5, nullptr), nullptr);
	}
	;

Condition : LogicExp {
        $$ = new_ast_node(ast_operator_type::AST_OP_CONDITION, $1, nullptr);
    }
    ;


ElseIf : IfBlock ELSE Block {
        $$ = insert_ast_node($1,new_ast_node(ast_operator_type::AST_OP_ELSE, $3, nullptr));
    }
	| IfBlock ELSE Statement {
		$$ = insert_ast_node($1,new_ast_node(ast_operator_type::AST_OP_ELSE, new_ast_node(ast_operator_type::AST_OP_BLOCK, $3, nullptr), nullptr));
	}
    | IfBlock ELSE ElseIf {
		$$ = insert_ast_node($1,new_ast_node(ast_operator_type::AST_OP_ELSE, $3, nullptr));
	}
	| IfBlock {
        $$ = $1;
	}
	;
 
WhileBlock : WHILE '(' Condition ')' Block {
        $$ = new_ast_node(ast_operator_type::AST_OP_WHILE, $3, $5, nullptr);
    }
    ;
/* 实参列表 */
RealParamList : Expr {
        $$ = create_contain_node(ast_operator_type::AST_OP_FUNC_REAL_PARAMS, $1);
    }
    | RealParamList ',' Expr {
        $$ = insert_ast_node($1, $3);
    }
    ;
%%

// 语法识别错误要调用函数的定义
void yyerror(char * msg)
{
    printf("Line %d: %s\n", yylineno, msg);
}
